0263. 丑数【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 迭代法
• 3. 🎯 s.2 - 递归法
• 4. 🔗 引用

1. 📝 题目描述

• leetcode

丑数 就是只包含质因数 2、3 和 5 的 正 整数。

给你一个整数 n，请你判断 n 是否为 丑数。如果是，返回 true ；否则，返回 false。

---

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7。

---

提示：

• -2^31 <= n <= 2^31 - 1

题目解读

• 丑数是指只包含质因数 2、3 和 5 的正整数。换句话说，丑数可以写成 2^a × 3^b × 5^c 的形式，其中 a、b、c 都是非负整数。
• 判断一个数是否为丑数的方法是：
  1. 如果数字小于等于 0，则不是丑数
  2. 不断地将数字除以 2、3、5，直到不能整除为止
  3. 如果最终结果是 1，则原数是丑数；否则不是

2. 🎯 s.1 - 迭代法

js

/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function (n) {
  // 丑数必须是正整数
  if (n <= 0) return false

  // 不断除以 2、3、5
  while (n !== 1) {
    if (n % 2 === 0) {
      n /= 2
    } else if (n % 3 === 0) {
      n /= 3
    } else if (n % 5 === 0) {
      n /= 5
    } else {
      // 如果不能被 2、3、5 整除，则不是丑数
      return false
    }
  }

  return true
}

js(更简洁)

/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function (n) {
  // 丑数必须是正整数
  if (n <= 0) return false

  // 分别除以 2、3、5 直到不能整除
  for (const factor of [2, 3, 5]) {
    while (n % factor === 0) {
      n /= factor
    }
  }

  // 如果最终结果是 1，则是丑数
  return n === 1
}

• 时间复杂度：$O(\log n)$，最坏情况下需要除法操作 $\log n$ 次
• 空间复杂度：$O(1)$

3. 🎯 s.2 - 递归法

js

/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function (n) {
  // 丑数必须是正整数
  if (n <= 0) return false

  // 1 是丑数
  if (n === 1) return true

  // 递归处理
  if (n % 2 === 0) return isUgly(n / 2)
  if (n % 3 === 0) return isUgly(n / 3)
  if (n % 5 === 0) return isUgly(n / 5)

  // 不能被 2、3、5 整除，则不是丑数
  return false
}

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(\log n)$，递归调用栈

4. 🔗 引用

• 丑数
  • 百度百科
• 质因数
  • 百度百科
• 算术基本定理（Fundamental Theorem of Arithmetic）
  • 百度百科
  • 任何一个大于 1 的整数，都可以唯一地分解成质因数的乘积。